/*
 * 1632. 二叉树的最大节点
 * 在二叉树中寻找值最大的节点并返回。
 * https://www.lintcode.com/problem/binary-tree-maximum-node/description
 * 
 * 样例
 * 给出如下一棵二叉树：
 * 		1
 * 	  /   \
 *  -5     2
 *  / \   /  \
 * 0   3 -4  -5 
 * 返回值为 3 的节点。
 */
package binary_tree_maximum_node_1632;

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * Definition of TreeNode:
 */
class TreeNode {
	public int val;
	public TreeNode left, right;
	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}

public class Binary_tree_maximum_node_1632 {
	/*
	 * @param root: the root of tree
	 * @return: the max node
	 */
	public static TreeNode maxNode(TreeNode root) {
		// write your code here
		TreeNode maxVal = new TreeNode(java.lang.Integer.MIN_VALUE);
		Queue<TreeNode> queue = new ArrayBlockingQueue<>(1000);
		if(root != null) {
			if(root.val > maxVal.val) {
				maxVal = root;
			}
			queue.add(root);
			while(queue.peek() != null) {
				if(queue.peek().left != null) {
					if(queue.peek().left.val > maxVal.val) {
						maxVal = queue.peek().left;
					}
					queue.add(queue.peek().left);
				}
				if(queue.peek().right != null) {
					if(queue.peek().right.val > maxVal.val) {
						maxVal = queue.peek().right;
					}
					queue.add(queue.peek().right);
				}
				queue.remove();
			}

		}
		else {
			maxVal = null;
		}
		System.out.println(maxVal.val);
		return maxVal;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//1 -5 2
		TreeNode root = new TreeNode(1);
		TreeNode p1 = new TreeNode(-5);
		TreeNode p2 = new TreeNode(2);
		root.left = p1;
		root.right = p2;
		System.out.println(maxNode(root).val);

	}

}
